/*
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
*/
//解决方案：当前节点之前的子串中：左括号的数量大于等于右括号的数量
//3ms
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void dfs(vector<string> & rst, string & element, int left, int right, int n)
{
    if (left + right == 2 * n && left == right) {
        rst.emplace_back(element);
        return;
    }
    if (left == right) {
        element.push_back('(');
        dfs(rst, element, left+1, right, n);
        element.pop_back();
    }
    if (left > right && left <= n && right <= n) {
        element.push_back('(');
        dfs(rst, element, left+1, right, n);
        element.pop_back();
        
        element.push_back(')');
        dfs(rst, element, left, right+1, n);
        element.pop_back();
    }
}

vector<string> generateParenthesis(int n)
{
    vector<string> rst;
    if (n < 1) {
        return rst;
    }
    int left = 0, right = 0;
    string element;
    dfs(rst, element, left, right, n);
    return rst;
}

int main(int argc, const char * argv[])
{
    generateParenthesis(3);
    return 0;
}
